We investigate an efficient teaching algorithm that adaptively picks these contrastive examples.

In other cases, the motivation may simply be to train more reliable classifiers.

We study the problem of active learning with the added twist that the learner is assisted by a helpful teacher. We consider the following natural interaction protocol: At each round, the learner proposes a query asking for the label of an instance $x^q$, the teacher provides the requested label $\{x^q, y^q\}$ along with explanatory information to guide the learning process. In this paper, we view this information in the form of an additional contrastive example ($\{x^c, y^c\}$) where $x^c$ is picked from a set constrained by $x^q$ (e.g., dissimilar instances with the same label). Our focus is to design a teaching algorithm that can provide an informative sequence of contrastive examples to the learner to speed up the learning process. We show that this leads to a challenging sequence optimization problem where the algorithm's choices at a given round depend on the history of interactions. We investigate an efficient teaching algorithm that adaptively picks these contrastive examples. We derive strong performance guarantees for our algorithm based on two problem-dependent parameters and further show that for specific types of active learners (e.g., a generalized binary search learner), the proposed teaching algorithm exhibits strong approximation guarantees. Finally, we illustrate our bounds and demonstrate the effectiveness of our teaching framework via two numerical case studies.

Sec. 3.2 a novel contribution [...] 4) l. 139: Is the teacher's reward the same as the reward previously defined for the

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. In this paper, the authors proposed a new active learning algorithm, which avoids the disagreement coefficient in the argument and label complexity. The proposed label complexity is also slight tighter than existing algorithm. Given a confidence-rated predictor with guaranteed error, the authors show how to use it to construct an active label query algorithm consistent in the agnostic setting. A novel confidence-rated predictor with guaranteed error that applies to any general classification problem is also proposed. They show that this predictor is optimal in the realizable case, in the sense that it has the lowest abstention rate out of all predictors that guarantee a certain error.

We present and analyze an agnostic active learning algorith m that works without keeping a version space. This is unlike all previous approac hes where a restricted set of candidate hypotheses is maintained throughout learn ing, and only hypotheses from this set are ever returned. By avoiding this version space approach, our algorithm sheds the computational burden and brittleness a ssociated with maintaining version spaces, yet still allows for substantial im provements over supervised learning for classification.

We investigate an efficient teaching algorithm that adaptively picks these contrastive examples.

We study the problem of active learning with the added twist that the learner is assisted by a helpful teacher. We consider the following natural interaction protocol: At each round, the learner proposes a query asking for the label of an instance x q, the teacher provides the requested label \{x q, y q\} along with explanatory information to guide the learning process. In this paper, we view this information in the form of an additional contrastive example ( \{x c, y c\}) where x c is picked from a set constrained by x q (e.g., dissimilar instances with the same label). Our focus is to design a teaching algorithm that can provide an informative sequence of contrastive examples to the learner to speed up the learning process. We show that this leads to a challenging sequence optimization problem where the algorithm's choices at a given round depend on the history of interactions.